\documentclass[UTF8]{ctexart}
\usepackage{xltxtra}
\usepackage{graphicx}
\usepackage{float}
\usepackage{subfigure}
%图片排版

\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}  
%\usepackage{algorithm}  
%\usepackage{algorithmicx}  
%\usepackage{algpseudocode}  
\usepackage{amsmath}

\title{图的模板类设计}
\author{陈乐瑶\\信息与计算科学 \quad 3210103710}
\date{\today}
\begin{document}
\maketitle
\pagestyle{plain}

\section{设计思路}
Graph类的设计主要包括属性和函数两部分，其中属性包括构成图的点类和边类，点和边的数量(需要维护),图的存储方式以及图的有向性。而函数主要包括两种存储方式下图的创建和输出，以及点和边的读入和列出。另外需要注意的是，如点和边的添加删除等动态操作函数由于不要求暂未列出，这些函数需要维护部分属性。

报告中由于篇幅限制，仅列出了有向图的结果，但无向图也经测试可完成所有程序功能。

\begin{itemize}
\item \textbf{储存类型的判断：}利用Mode函数区分，自动判断时以$|E|=|V|log|V|$为分界点。
\item \textbf{点和边类的设计：}利用struct设计，利用数组存储。
\item \textbf{邻接表和邻接矩阵的设计：}邻接表可直接利用存储的数组，邻接矩阵单独写出一个空的二维数组。
\item \textbf{函数的设计：}$PrintGraph$根据Mode判断储存类型后生成图，$ListVertexes$列出所有点，$ListEdges$列出所有边。
\end{itemize}  

\section{测试说明}
\subsection{程序功能测试}
以上课使用的图为例(图源智云课堂)，Vname类型为int，weight类型为double。

测试图的生成、listVertexes以及listEdges函数的实现：
\begin{figure}[htbp]
  \centering
  \includegraphics[scale=0.6]{fig2.png}
  \caption{示意图例}
\end{figure}

\subsubsection{mode=0:邻接表/mode=1:邻接矩阵}
（邻接矩阵这里老师写的有点怪，不重要）

（为了两页放得下进行了一些压缩，不重要）             

\begin{figure}[htbp]
  \centering
  \begin{minipage}{0.49\linewidth}
    \centering
  {
    \includegraphics[width=4cm]{fig211.png}}
  \hspace{0in}
  {
    \includegraphics[width=4cm]{fig212.png}}
  \caption{邻接表测试结果（左）及课堂展示图（右）}
  \end{minipage}
  \begin{minipage}{0.49\linewidth}
    \centering
  {
    \includegraphics[width=4cm]{fig221.png}}
  \hspace{0in}
  {
    \includegraphics[width=4cm]{fig222.png}}
  \caption{邻接矩阵测试结果（左）及课堂展示图（右）}
  \end{minipage}  
\end{figure}

\subsubsection{mode=-1:自动判断}
如上，$|V|=4,|E|=5,|E|<|V|×ln|V|$判断为邻接表

任意添加一条边，$|V|=4,|E|=6,|E|\geq|V|×ln|V|$判断为邻接矩阵

\begin{figure}[htbp]
  \centering
  {
    \includegraphics[width=4cm]{fig231.png}}
  \hspace{0in}
  {
    \includegraphics[width=4cm]{fig232.png}}
  \caption{邻接表和邻接矩阵的判断测试结果}
\end{figure}

经测试，程序功能能够实现。

\subsection{内存泄漏测试}
\begin{figure}[htbp]
  \centering
  \includegraphics[scale = 0.4]{fig3.png}
  \caption{内存泄漏测试}
\end{figure}
经测试说明，无内存泄漏，程序安全。

\end{document}
